package com.sx.sx1.lintcode.day717;

public class LC1451 {

    static class Solution {
        /**
         * @param seats: an array
         * @return: the maximum distance
         */
        public int maxDistToClosest(int[] seats) {
            //双指针
            int ans =0;
            int n = seats.length;
            for (int i = 0; i <n ; i++) {
                if(seats[i] ==0){
                    int stepsl =0,stepsr =0;
                    int left =i;
                    //往左扩
                    while (left>=0){
                        if(seats[left] ==1) break;
                        left--;
                        stepsl++;
                    }
                    int right =i;
                    //往右扩
                    while (right<n){
                        if(seats[right] ==1) break;
                        right++;
                        stepsr++;
                    }

                   if(i ==0){  //i=0时不能往左扩，不用比较左边的
                       ans =Math.max(ans,stepsr);
                   }else if(i<n-1){
                       //i> 0 && i<n-1 两边都可以扩
                       ans = Math.max(ans,Math.min(stepsl,stepsr));
                   }else if(i==n-1){
                       //i=n-时不能往右扩，不用比较右边的
                       ans = Math.max(ans,stepsl);
                   }

                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxDistToClosest(new int[]{1,0,0,0,1,0,1})); //2
        System.out.println(new Solution().maxDistToClosest(new int[]{1,0,0,0})); //3
    }


    static class Solution1 {
        /**
         * @param seats: an array
         * @return: the maximum distance
         */
        public int maxDistToClosest(int[] seats) {
            int ans = 0;
            for (int i = 0; i < seats.length; i++) {
                if (seats[i] == 0) {
                    int left = 0, right = 0;
                    int L = i;
                    while (L >= 0) { //看左边到最近的人多远
                        if (seats[L] == 1) {
                            break;
                        }
                        L--;
                        left++;
                    }

                    int R = i;
                    while (R < seats.length) {//看右边到最近的人多远
                        if (seats[R] == 1) break;
                        R++;
                        right++;
                    }

                    if (i == 0) { //第一个位置的时候不能往左边扩
                        ans = Math.max(ans, right);
                    } else if (i < seats.length - 1) {
                        //中间位置的时候技能往左边括，也能往右边括，左右两边括取最小
                        ans = Math.max(ans, Math.min(left, right));
                    }
                    if (i == seats.length - 1) { //最后一个位置的时候不能往右边扩
                        ans = Math.max(ans, left);
                    }
                }
            }
            return ans;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有207条未读消息，请及时查看
1451 · 到最近的人的最大距离
算法
简单
通过率
50%

题目
题解17
笔记
讨论11
排名
记录
描述
在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。

至少有一个空座位，且至少有一人坐在座位上。

亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。

返回他到离他最近的人的最大距离。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1 <= seats.length <= 20000
seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
样例
样例 1:

输入：[1,0,0,0,1,0,1]
输出：2
解释：
如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
因此，他到离他最近的人的最大距离是 2 。
样例 2:

输入：[1,0,0,0]
输出：3
解释：
如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
这是可能的最大距离，所以答案是 3 。
标签
企业
Google
相关题目

1513
考场就座
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
15 分 00 秒
123456789

控制台
        历史提交

 */
